package leetcode.editor.cn.dsa03_stack;
//删除最外层的括号
public class RemoveOutermostParentheses1021_3 {
    public static void main(String[] args) {
        Solution solution = new RemoveOutermostParentheses1021_3().new Solution();
        String[] arr = {"(()())(())", "(()())(())(()(()))", "()()"};
        for (int i = 0; i < arr.length; i++) {
            String ret = solution.removeOuterParentheses(arr[i]);
            System.out.println(arr[i] + "====>" + ret);
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 最优解：栈解法
         * 1.使用数组模拟一个栈，临时存储左括号字符
         *   push(Character) ; pop(); isEmpty()
         * 2.遍历字符串，根据情况进行入栈/出栈操作栈实现代码：
         *   读取到左括号，左括号入栈
         *   读取到右括号，左括号出栈
         * 3.判断栈是否为空，若为空，找到了一个完整的原语
         * 4.截取不含最外层括号的原语子串并进行拼接
         *
         * @param str
         * @return
         */
        public String removeOuterParentheses(String str) {
            StringBuilder result = new StringBuilder();
            // 1.直接用数组取代栈
            int len = str.length();
            char[] stack = new char[len];
            int index = -1; // 栈顶索引
            char[] array = str.toCharArray();
            // 2.遍历字符串，根据情况进行入栈 / 出栈操作
            for (int i = 0; i < len; i++) {
                char c = array[i];
                if (c == '(') { // 遇到左括号，左括号入栈
                    // 3.去掉截取子串的操作，将原语字符直接拼接
                    if(index > -1){ // 此前有数据，当前必属原语
                        result.append(c);
                    }
                    stack[++index] = c;
                } else { // 遇到右括号，左括号出栈
                    stack[index--] = '\u0000';
                    if(index > -1){
                        result.append(c);
                    }
                }
            }
            return result.toString();
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}
